#include "my_heap.h"
#include <stdio.h>
#include <stdlib.h>
#include <math.h>

#define PRINT_LIST		1

#define WSIZE			4	//1字=4字节
#define DSIZE			8	

#define MIN_BLK_SIZE	16		//最小块大小

#define MASK			0x03					//对齐掩码

#ifndef HEAP_SIZE
#define HEAP_SIZE		(8*1024*1024)		//堆最大大小
#endif

#define CHUNKSIZE		(1<<12)			//brk一次增长大小

#define GET(ptr)		(*((unsigned int*)(ptr)))		
#define SET(ptr,val)	(*((unsigned int*)(ptr))=(val))
#define HEAD(ptr)		(ptr-WSIZE)						//块头部
#define GET_SIZE(ptr)	(GET(HEAD(ptr))&~MASK)				//块大小
#define FOOT(ptr)		(ptr+GET_SIZE(ptr)-DSIZE)		//块尾部

#define NEXT_BLK(ptr)		(FOOT(ptr)+DSIZE)			//后继内存块
#define PREV_BLK(ptr)		(ptr-GET_SIZE(ptr-WSIZE))	//前驱内存块
#define NEXT_FREE_BLK(ptr)	(GET(ptr+WSIZE))			//后继空闲块
#define PREV_FREE_BLK(ptr)	(GET(ptr))					//前驱空闲块

//#define LIST_HEAD(size)	(list_index(size))

#define IS_ALLOC(ptr)	(GET(HEAD(ptr))&0x01)
#define ALLOC(ptr)		(SET(HEAD(ptr),GET_SIZE(ptr)|0x01));(SET(FOOT(ptr),GET_SIZE(ptr)|0x01))
#define FREE(ptr)		(SET(HEAD(ptr),GET_SIZE(ptr)&~0x01));(SET(FOOT(ptr),GET_SIZE(ptr)&~0x01))

//空闲链表数组
#define MAX_FREE_LIST_CNT  14    //1~4096~+oo
static void *free_list[MAX_FREE_LIST_CNT];

static void *heap_beg = NULL;		//堆空间起始地址	
static void *heap_end = NULL;		//堆空间结束地址
static void *heap_list = NULL;		//序言块的下个快
static void *brk = NULL;			//堆顶指针

static int free_index(size_t size)
{
	int i=0;

	if(size > pow(2,MAX_FREE_LIST_CNT-2))
		return MAX_FREE_LIST_CNT-1;
	
	size-=1;
	while(size)
	{
		size >>= 1;
		i++;
	}

	return i;
}

static void print_list()
{
#ifdef PRINT_LIST
	int i=0;
	void *ptr = PREV_BLK(heap_list);

	printf("no	size alloc\n");	
	while(GET_SIZE(ptr))
	{
		printf("%d	%d	%d\n",++i, GET_SIZE(ptr), IS_ALLOC(ptr));
		ptr = NEXT_BLK(ptr);
	}
	printf("%d	%d	%d\n\n",++i, GET_SIZE(ptr), IS_ALLOC(ptr));
#endif
}


static void *sbrk(int inc)
{
	void *old_brk = brk;

	if(inc<=0||brk+inc>heap_end)
	{
		fprintf(stderr, "can't increase heap\n");
		return (void *)-1; 		
	}
	brk += inc;

	return old_brk;
}

//将空闲块从空闲链表移除
static void remove(void *ptr)
{
	
}

//合并空闲块
static void* merge(void *ptr)
{
	void *pre=PREV_BLK(ptr), *next=NEXT_BLK(ptr);
	int pre_alloc=IS_ALLOC(pre), next_alloc=IS_ALLOC(next);

	//前驱后继非空闲
	if(pre_alloc && next_alloc)
	{
	}
	//前驱空闲，后继非空闲
	else if(!pre_alloc && next_alloc)
	{
		SET(HEAD(pre),GET_SIZE(pre)+GET_SIZE(ptr));
		SET(FOOT(pre),GET_SIZE(pre));
		ptr = pre;
	}
	//前驱非空闲，后继空闲
	else if(pre_alloc && !next_alloc)
	{
		SET(HEAD(ptr),GET_SIZE(ptr)+GET_SIZE(next));
		SET(FOOT(ptr),GET_SIZE(ptr));
	}
	//前驱后继空闲
	else	
	{
		SET(HEAD(pre),GET_SIZE(pre)+GET_SIZE(ptr)+GET_SIZE(next));
		SET(FOOT(pre),GET_SIZE(pre)+GET_SIZE(ptr));
		ptr = pre;
	}

	return ptr;
}

//首次适配算法
static void *first_fit(size_t size)
{
	int index = free_index(size);	//定位空闲链表
	void* ptr = free_list[index];

	while(ptr!=NULL && GET_SIZE(ptr)<size)
	{
		ptr = NEXT_FREE_BLK(ptr);
	}

	return ptr;
}


static void *find_fit(size_t size)
{
	void *ptr=NULL;

#if defined FIRST_FIT
	ptr=first_fit(size);
#elif defined NEXT_FIT
	ptr=next_fit(size);
#elif defined BEST_FIT
	ptr=best_fit(size);
#elif defined WREST_FIT
	ptr=wrest_fit(size);
#else
	ptr=first_fit(size);
#endif

	return ptr;
}

//将空闲块插到合适的空闲链表中的合适位置
static void insert(void *ptr)
{
	int size = GET_SIZE(ptr);
	int index = free_index(size);
	void *pb = free_list[index];

	while(pb!=NULL && GET_SIZE(pb)<size)
	{
		pb = NEXT_FREE_BLK(pb);
	}
	SET(ptr, pb);
	
	if(pre == free_list[index])
		SET(free_list[index], ptr);
	else
		SET(pre, ptr);
}

//分割块
static void place(void *ptr, size_t size)
{
	size_t blk_size = GET_SIZE(ptr);
	void *next;
	
	if(blk_size-size>=MIN_BLK_SIZE)
	{
		next = ptr+size;
		SET(HEAD(next), blk_size-size);
		SET(FOOT(next), blk_size-size);
		FREE(next);
		insert(next, blk_size-size);
	}
	else
	{
		size = blk_size;
	}

	SET(HEAD(ptr), size);
	SET(FOOT(ptr), size);
	ALLOC(ptr);	
}

static void* extend_heap(int words)
{
	void *old_brk;

	if((old_brk=sbrk(words*WSIZE))==(void *)-1)
	{
		return (void *)-1;
	}
		
	SET(HEAD(old_brk), words*WSIZE);	//头
	SET(FOOT(old_brk), words*WSIZE);	//尾
	SET(HEAD(brk), 0x01);				//新尾哨兵
		
	return merge(old_brk);	
}

void *my_malloc(size_t size)
{
	void *ptr=NULL;
	int inc;

	if(size<=0)
	{
		fprintf(stderr, "size much >= 0\n");
		return NULL;
	}	
	
	size=(size+DSIZE+MASK)&~MASK;
	if((ptr=find_fit(size))==NULL)
	{
		inc=(size+CHUNKSIZE-1)&~(CHUNKSIZE-1);
		if((ptr=extend_heap(inc/WSIZE))==(void *)-1)
		{
			return NULL;
		}
	}
	place(ptr,size);
	print_list();

	return ptr;
}

void my_free(void *ptr)
{
	if(ptr<=heap_beg||ptr>=brk)
	{
		fprintf(stderr,"ptr invalue\n");
		return;
	}

	FREE(ptr);
	merge(ptr);
	
	print_list();
}

int my_mem_init()
{
	if((heap_beg=brk=malloc(HEAP_SIZE))==NULL)
	{	
		fprintf(stderr, "Can't applicate memory\n");
		return -1;
	}
	heap_end = heap_beg+HEAP_SIZE;	

	sbrk(4*WSIZE);	
	SET(heap_beg+WSIZE, 0x09);	//前哨兵头		
	SET(heap_beg+DSIZE, 0x09);	//前哨兵尾
	SET(heap_beg+3*WSIZE, 0x01);	//后哨兵头	
	heap_list = brk;	

	if(extend_heap(CHUNKSIZE/WSIZE)==(void *)-1)
	{
		fprintf(stderr, "Can't extend heap\n");
		return -1;
	}
	printf("mem_init success\n");

	return 0;
}
